package algorithm;

import java.util.ArrayList;

public class leetcode_0020 {
    public static void main(String[] args) {
        String s="()";
    }
    public boolean isValid(String s) {
        ArrayList<Integer> list=new ArrayList<>();

        if(s=="") return true;
        char[] str=s.toCharArray();
        int len=str.length;
        if(len%2!=0) return false;
        int current=1;
        if(str[0]==')'||str[0]==']'||str[0]=='}') return false;
        list.add(change(str[0]));
        for(int i=1;i<len;++i){
            int a=change(str[i]);
            if(a>0){
                if(current==0||list.get(current-1)+a!=0) return false;
                list.remove(--current);
            }
            else{
                list.add(a);current++;
            }
        }
        if(current==0) return true;
        return false;
    }
    public int change(char a){
        if(a=='(') return -1;
        else if(a==')') return 1;
        else if(a=='[') return -2;
        else if(a==']') return 2;
        else if(a=='{') return -3;
        else  return 3;
    }
}
